// Testing performance of std::set vs. std::vector
// By Sean Heber <sean at fifthace.com>
// http://www.bigzaphod.org/
// License: Public Domain
// December 2005

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <sys/time.h>

static struct _ticks_global {
  struct timeval start;
  _ticks_global() { gettimeofday(&start, NULL); }
} ticks_global;

unsigned int ticks()
{
  struct timeval now;
  gettimeofday(&now, NULL);
  return (now.tv_sec-ticks_global.start.tv_sec)*1000+(now.tv_usec-ticks_global.start.tv_usec)/1000;
}

int main( int argc, char* argv[] )
{
  const int		SIZE_OF_ARRAY = argc>1? strtol(argv[1], NULL, 10): 10;
  const int		NUMBER_OF_TESTS = argc>2? strtol(argv[2], NULL, 10): 100;
  const int		NUMBER_OF_CYCLES = argc>3? strtol(argv[3], NULL, 10): 1000;
  std::set<int>		int_set;
  std::vector<int>	int_vec;
  std::vector<int>	set_time, vec_time;
  int			blah;

  std::cout << SIZE_OF_ARRAY << " elements in each container." << std::endl;
  std::cout << "Running " << NUMBER_OF_TESTS << " tests with " << NUMBER_OF_CYCLES << " cycles each." << std::endl;

  set_time.reserve(NUMBER_OF_CYCLES*NUMBER_OF_TESTS);
  vec_time.reserve(NUMBER_OF_CYCLES*NUMBER_OF_TESTS);
  // this runs the main test for the specified number of times and cycles
  // note that I'm searching between -1 and 1+SIZE_OF_ARRAY in each test
  // the idea is to fairly take into account the worst case scenerio of
  // a number not appearing in the container

  for( int z=0; z<NUMBER_OF_TESTS; z++ ) {

    int t = ticks();
    for( int i=(SIZE_OF_ARRAY-1); i>-1; i-- ) 
      int_set.insert( i );

    int c;
    for( c=0; c<NUMBER_OF_CYCLES; c++ ) {
      int j;
      for( j=-1; j<SIZE_OF_ARRAY+1; j++ ) {
        std::set<int>::iterator n = int_set.find( j );
        if( n != int_set.end() )
          blah = *n;
      }
      for( j=SIZE_OF_ARRAY+1; j>-1; j-- ) {
        j--;
        std::set<int>::iterator n = int_set.find( j );
        if( n != int_set.end() )
          blah = *n;
      }
    }

    set_time.push_back( ticks()-t );
    int_set.clear();

    t = ticks();
    int_vec.reserve(SIZE_OF_ARRAY+2);

    for( int i=(SIZE_OF_ARRAY-1); i>-1; i-- ) 
      int_vec.push_back( i );
    //for( int i=0;i<SIZE_OF_ARRAY; i++ ) 
    //  int_vec.push_back( i );
    
    std::sort(int_vec.begin(), int_vec.end());
    std::unique(int_vec.begin(), int_vec.end());    

    for( c=0; c<NUMBER_OF_CYCLES; c++ ) {
      int j;
      for( j=-1; j<SIZE_OF_ARRAY+1; j++ ) {

        std::vector<int>::iterator n = std::lower_bound(int_vec.begin(), 
                                                        int_vec.end(), j);
        if ( n != int_vec.end() )
          blah = *n;
      }
      for( j=SIZE_OF_ARRAY+1; j>-1; j-- ) {
        j--;

        std::vector<int>::iterator n = std::lower_bound(int_vec.begin(), 
                                                        int_vec.end(), j);
        if ( n != int_vec.end() )
          blah = *n;
      }
    }
    
    vec_time.push_back( ticks()-t );
    int_vec.clear();
  }

  // using blah to make sure the compiler doesn't optimize it out of the equation
  while( blah ) blah--;

  std::vector<int>::iterator i;
  double set_avg, vec_avg;
  set_avg = vec_avg = 0;

  std::cout << "iter = " << set_time.size() << "  " << vec_time.size() << std::endl;

  for( i=set_time.begin(); i!=set_time.end(); i++ ) 
    set_avg += *i;
  set_avg /= (double)set_time.size();

  for( i=vec_time.begin(); i!=vec_time.end(); i++ ) 
    vec_avg += *i;
  vec_avg /= (double)vec_time.size();

  std::cout << "Average per test for SET:\t" << set_avg << " ms";
  if( set_avg < vec_avg ) std::cout << " [winner]";
  std::cout << std::endl;
  std::cout << "Average per test for VECTOR:\t" << vec_avg << " ms";
  if( vec_avg < set_avg ) std::cout << " [winner]";
  std::cout << std::endl;

  return 0;
}
